# 15/100 数组-合并区间
# leetcode第189题: https://leetcode.cn/problems/rotate-array/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/11/29
import copy

from leetcode import test


def rotate_outplace(nums: list[int], k: int) -> list[int]:
    """使用额外的空间"""
    n = len(nums)
    if n < 2 or k == 0:
        return nums

    nums_copy = copy.deepcopy(nums)
    for i in range(n):
        nums[i] = nums_copy[(i - k) % n]
    return nums


def rotate_slice(nums: list[int], k: int) -> list[int]:
    """使用切片"""
    n = len(nums)
    k = k % n
    # 注意, 不能使用nums = nums[-k:] + nums[:-k], 因为这样的赋值方式直接改变了nums的地址. 而nums[:]即使用切片创建副本
    nums[:] = nums[-k:] + nums[:-k]
    return nums[:]


def retate_reverse(nums: list[int], k: int) -> list[int]:
    n = len(nums)
    k = k % n  # 防止 k 超过数组长度

    # 辅助函数：反转数组的一部分
    def reverse(start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

    # 三次反转
    reverse(0, n - 1)  # 整体反转
    reverse(0, k - 1)  # 反转前 k 个
    reverse(k, n - 1)  # 反转后 n-k 个
    return nums


if __name__ == '__main__':
    inp = [{"nums": [1, 2, 3, 4, 5, 6, 7], "k": 3}, {"nums": [-1, -100, 3, 99], "k": 2}, {"nums": [1, 2], "k": 3},
           {"nums": [1, 2, 3], "k": 4}, ]
    out = [[5, 6, 7, 1, 2, 3, 4], [3, 99, -1, -100], [2, 1], [3, 1, 2]]

    test.test_function(rotate_outplace, inp, out)
    test.test_function(rotate_slice, inp, out)
    test.test_function(retate_reverse, inp, out)
